#
# @lc app=leetcode.cn id=100 lang=python3
#
# [100] 相同的树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        #solution1:递归法
        # def isSameT(l,r):
        #     if l == None and r == None:
        #         return True
        #     elif l == None or r == None:
        #         return False
        #     elif l.val != r.val:
        #         return False
        #     elif isSameT(l.left,r.left) and isSameT(l.right,r.right):
        #         return True
        #     else:
        #         return False
        
        # return isSameT(p,q)
        
        #solution2:队列
        nodeList = []
        nodeList.append(p)
        nodeList.append(q)
        
        while nodeList != []:
            l = nodeList.pop(0)
            r = nodeList.pop(0)
            if l == None and r == None:
                continue
            elif l == None or r == None:
                return False
            elif l.val != r.val:
                return False
            else:
                nodeList.append(l.left)
                nodeList.append(r.left)
                nodeList.append(l.right)
                nodeList.append(r.right)
        
        return True                
            
        
        
        
# @lc code=end

